`
https://leetcode.cn/problems/dungeon-game/
`

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
var calculateMinimumHP = function (dungeon) {
  const m = dungeon.length, n = dungeon[0].length
  const memo = new Array(m).fill().map(() => new Array(n).fill(-1))

  // dp[i][j] 表示从 dp[i][j] 走到 dp[m-1][n-1] 所需的最少血量
  function dp(i, j) {
    // 到终点了，保证到终点时血不会扣完
    if (i === m - 1 && j === n - 1) {
      return dungeon[i][j] > 0 ? 1 : 1 - dungeon[i][j]
    }

    // 防止越界
    if (i >= m || j >= n) {
      return Infinity
    }

    // 如果已经计算过
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }

    // 拿到需要更少血量的路径
    memo[i][j] = Math.min(
      dp(i + 1, j),
      dp(i, j + 1)
    ) - dungeon[i][j]

    // 保证血量不低于 1
    memo[i][j] = memo[i][j] <= 0 ? 1 : memo[i][j]

    return memo[i][j]
  }

  return dp(0, 0)
};